package DataStructures;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyLinkedList<T> implements Iterable<T> {
	private int theSize;
	private int modCount = 0;
	private Node<T> beginMaker;
	private Node<T> endMaker;
	private static class Node<T> {
		public Node(T d, Node<T> p, Node<T> n) {
			data = d;
			prev = p;
			next = n;
		}
		
		public T data;
		public Node<T> prev;
		public Node<T> next;
	}
	
	public MyLinkedList() {
		clear();
	}
	
	public void clear() {
		beginMaker = new Node<T>(null, null, null);
		endMaker   = new Node<T>(null, beginMaker, null);
		beginMaker.next = endMaker;
		
		theSize = 0;
		modCount++;
	}
	public int size() {
		return theSize;
	}
	public boolean isEmpty() {
		return size() == 0;
	}
	public boolean add(T x) {
		add(size(), x);
		return true;
	}
	public void add(int idx, T x) {
		addBefore(getNode(idx), x);
	}
	public T get(int idx) {
		return getNode(idx).data;
	}
	public T set(int idx, T newVal) {
		Node<T> node = getNode(idx);
		T oldVal = node.data;
		node.data = newVal;
		return oldVal;
	}
	public T remove(int idx) {
		return remove(getNode(idx));
	}
	
	private void addBefore(Node<T> p, T x) {
		Node<T> tmpNode = new Node<T>(x, p.prev, p);
		p.prev.next = tmpNode;
		p.prev = tmpNode;
		theSize++;
		modCount++;
	}
	private T remove(Node<T> p) {
		p.prev.next = p.next;
		p.next.prev = p.prev;
		theSize++;
		modCount++;
		
		return p.data;
	}
	private Node<T> getNode(int idx) {
		Node<T> tmpNode;
		
		if(idx < size()/2) {
			tmpNode = beginMaker.next;
			for(int i = 0; i < idx; i++)
				tmpNode = tmpNode.next;
		} else if(idx >= size()/2 && idx <= size()) {
			tmpNode = endMaker;
			for(int i = size(); i > idx; i--)
				tmpNode = tmpNode.prev;
		} else throw new IndexOutOfBoundsException();
		
		return tmpNode;
	}
	//exercise 3.3
	public boolean contains(T x) {
		Node<T> tmpNode = beginMaker.next;
		
		while(tmpNode != endMaker && !tmpNode.data.equals(x))
			tmpNode = tmpNode.next;
//		if(tmpNode != endMaker)
//			return true;
//		else 
//			return false;
		return tmpNode != endMaker;
	}
	
	//exercise 3.10  O(n**2)
	public void removeAll(Iterable<? extends T> items) {
		Iterator<? extends T> itr = items.iterator();
		Node<T> tmpNode = beginMaker.next;
		
		while(itr.hasNext()) {
			T itrData = itr.next();
			while(tmpNode != endMaker && tmpNode.data.equals(itrData))
				tmpNode = tmpNode.next;
			if(tmpNode != endMaker)
				remove(tmpNode);
		}
	}
	//3.18
	public void addFirst(T x) {
		addBefore(beginMaker.next, x);
	}
	public void addLast(T x) {
		addBefore(endMaker, x);
	}
	public void removeFirst() {
		remove(beginMaker.next);
	}
	public void removeLast() {
		remove(endMaker.prev);
	}
	public T getFirst() {
		return getNode(0).data;
	}
	public T getLast() {
		return getNode(size() - 1).data;
	}
	
	public Iterator<T> iterator() {
		return new LinkedListIterator();
	}
	private class LinkedListIterator implements Iterator<T> {
		private Node<T> current = beginMaker.next;
		private int expectedModCount = modCount;
		public boolean okToRemove = false;
		
		public boolean hasNext() {
			return current != endMaker;
		}
		
		public T next() {
			if(modCount != expectedModCount)
				throw new ConcurrentModificationException();
			if(!hasNext()) 
				throw new NoSuchElementException();
			
			T nextItem = current.data;
			current = current.next;
			okToRemove = true;
			return nextItem;
		}
		
		public void remove() {
			if(modCount != expectedModCount)
				throw new ConcurrentModificationException();
			if(!okToRemove)
				throw new IllegalStateException();
			
			MyLinkedList.this.remove(current.prev);
			okToRemove = false;
			expectedModCount++;
		}
	}
}
